1. Field of the Invention
The present invention generally relates to cache systems, and particularly relates to a cache system having a hierarchical cache memory structure.
2. Description of the Related Art
In computer systems, generally, a cache memory characterized by its small capacity and high speed is provided separately from the main memory. Part of the information stored in the main memory is copied to the cache. When this part of the information is to be accessed, it is retrieved from the cache rather than from the main memory, thereby achieving high-speed information retrieval.
A cache includes a plurality of cache lines. Copying of information from the main memory to the cache is performed in the units of cache lines. The memory space of the main memory is divided in the units of cache lines, and the divided memory areas are assigned to corresponding cache lines successively. Since the capacity of the cache is smaller than the capacity of the main memory, the memory areas of the main memory are assigned to the same cache lines repeatedly.
When a first access is performed with respect to a given address in the memory space, information (data or program) stored at this address is copied to the corresponding cache line in the cache. When a next access is performed with respect to the same address, the information is directly retrieved from the cache.
One cache line may be 32-byte long. In this case, for example, the five least significant bits of an address indicate an address offset, and a predetermined number of higher order bits adjacent to these bits indicate an index. The remaining further higher order bits indicate a cache tag.
When data is to be accessed, an index portion of the address indicating the access destination is used to read a tag associated with the corresponding index in the cache. A check is then made as to whether the retrieved tag matches the bit pattern of the tag portion of the address. If they do not match, a cache miss is detected. If they match, cache data (32-byte data equal in amount to one cache line) corresponding to the index is accessed. In the case of read operation, one byte of the 32-byte data is selected as indicated by the offset portion of the address, and is used as read data retrieved from the cache.
A cache configuration in which only one tag is provided for each cache line is referred to as a direct mapping method. A cache configuration in which N tags are provided for each cache line is referred to as an N-way set associative method. The direct mapping method can be regarded as a one-way set associative method.
In a write-through method, data writing is performed to the main memory as well as to a cache when the data needs to be written to memory. In this method, when there is a need to replace the contents of the cache, all that is necessary is to set a valid bit indicative of the valid/invalid state of the data to an invalid state. In a write-back method, on the other hand, data writing is performed only with respect to a cache when the data needs to be written to memory. Since the written data exists only in the cache memory, the contents of the cache memory need to be copied to the main memory when these contents in the cache are to be replaced.
In order to lessen a penalty associated with accessing the main memory at the time of a cache miss, a system with a hierarchical cache memory arrangement is used. For example, a secondary cache allowing a faster access than access to the main memory may be provided between a primary cache and the main memory. With this provision, the frequency of necessary accesses to the main memory is reduced at the time of the occurrence of a cache miss with respect to the primary cache, thereby lessening the cache miss penalty.
The configuration of a multi-level cache system may be classified mainly into three types as in the following from the viewpoint of the inclusion property of data between the caches. In the following, a two-level cache hierarchy is taken as an example, with the one closer to the computing unit being a primary cache, and the one closer to the main memory being a secondary cache. In general, a primary cache is characterized by its small capacity and high speed, and a secondary cache is characterized by its large capacity and low speed.
(1) Inclusive Cache
An inclusive cache refers to a cache system in which all the contents of the primary cache are stored in the secondary cache without exception. Namely, the contents of the secondary cache include the contents of the primary cache. This is the simplest configuration, and has an advantage in that logic for controlling the operation of the caches is easy to implement. A drawback is that an effective cache size is smaller than the total size of the caches (i.e., the size of the secondary cache+the size of the primary cache), and is limited to the size of the secondary cache at the maximum.
(2) Exclusive Cache
An exclusive cache refers to a cache system in which all the cache contents are only stored either in the primary cache or in the secondary cache. Namely, the contents of the primary cache and the contents of the secondary cache are exclusive to each other. The effective cache size is equal to the total size of the caches, which means that the highest memory utilization in the three methods is achieved. However, various demerits are in existence in terms of control operations, such as a need to make the secondary cache reflect all the replacements of contents of the primary cache. When the replacement of contents of the primary cache occurs frequently, further, it hampers data supply to the computing unit, which may results in lower performance.
(3) Non-Inclusive Cache (Partially Inclusive Cache)
A non-inclusive cache refers to a cache system which is basically an inclusive cache, but does not require the sustaining of inclusive property as an absolute requirement, thereby allowing the presence of a state in which a content of the primary cache is not included in the secondary cache. The non-inclusive cache may also refer to a cache system which is basically an exclusive cache, but does not require the sustaining of exclusive property as an absolute requirement, thereby allowing the presence of a state in which a content of the primary cache is included in the secondary cache. The effective cache size is between that of the inclusive cache and that of the exclusive cache. Difficulty associated with the implementation of control operation is also midlevel. Since there is not a strong demand for the processes for sustaining the inclusive property (or exclusive property), the lowering of performance of the primary cache associated with such processes may be reduced.
In the field of embedded processors, there is also a tendency that hierarchical cache systems are generally used. In the field of embedded processors, the cost of chip area size is extremely high, which requires the efficient use of RAMs implemented in the chip. From this viewpoint, the non-inclusive cache is more preferable than the inclusive cache, and the exclusive cache is more preferable than the non-inclusive cache. Since the time period typically spent on the development of chips in the field of embedded processors is very short, the exclusive cache is not a desirable system since the exclusive cache requires a large number of development steps and check steps.
Especially in the field of embedded processors, a system such as the non-inclusive cache having a relatively short development period and achieving a relatively efficient use of cache memory is desirable.
An example of the non-inclusive cache is disclosed in Patent Document 1. Further, Patent Document 2 discloses a system that reduces invalidating operations directed from the secondary cache to the primary cache in respect of cache inclusion property.
In the system disclosed in Patent Document 1, in order to achieve the non-inclusive cache effectively, information indicative of whether the contents of the primary cache are included in the secondary cache needs to be added to the tags of the primary cache. This enhances the effect of the non-inclusive system in that its control operations are easy, but necessitates an additional logic for the primary cache, which may result in an increase in the number of development steps.
[Patent Document 1] U.S. Pat. No. 5,564,035
[Patent Document 2] Japanese Patent Application Publication No. 6-161887
[Patent Document 3] Japanese Patent No. 2905118
[Patent Document 4] Japanese Patent Application Publication No. 5-324473
Accordingly, there is a need for a non-inclusive-type cache system that is easy to implement.